SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Programming Computable Functions</title>

</head>

Programming Computable Functions

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .infobox-subbox{padding:0;border:none;margin:-3px;width:auto;min-width:100%;font-size:100%;clear:none;float:none;background-color:transparent}.mw-parser-output .infobox-3cols-child{margin:auto}.mw-parser-output .infobox .navbar{font-size:100%}@media screen{html.skin-theme-clientpref-night .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media(min-width:640px){body.skin--responsive .mw-parser-output .infobox-table{display:table!important}body.skin--responsive .mw-parser-output .infobox-table>caption{display:table-caption!important}body.skin--responsive .mw-parser-output .infobox-table>tbody{display:table-row-group}body.skin--responsive .mw-parser-output .infobox-table th,body.skin--responsive .mw-parser-output .infobox-table td{padding-left:inherit;padding-right:inherit}}

/* end https://en.wikipedia.org/ */

</style><table class="infobox vevent"><tbody><tr><th colspan="2" class="infobox-above" style="background-color:#e0e0e0;">Programming Computable Functions</th></tr><tr><th scope="row" class="infobox-label"><a href="Programming_paradigm" title="Programming paradigm">Paradigm</a></th><td class="infobox-data"><a href="Functional_programming" title="Functional programming">functional</a></td></tr><tr><th scope="row" class="infobox-label"><a href="Software_design" title="Software design">Designed by</a></th><td class="infobox-data"><a href="Dana_Scott" title="Dana Scott">Dana Scott</a>, <a href="Robin_Milner" title="Robin Milner">Robin Milner</a>, <a href="Gordon_Plotkin" title="Gordon Plotkin">Gordon Plotkin</a></td></tr><tr><th scope="row" class="infobox-label">First appeared</th><td class="infobox-data">December 1977 (1977-12)</td></tr><tr><td colspan="2" class="infobox-full-data"></td></tr><tr><th scope="row" class="infobox-label" style="white-space: nowrap;"><a href="Software_release_life_cycle" title="Software release life cycle">Final release</a></th><td class="infobox-data"><div style="margin:0px;">Full Abstraction

/ 15 December 2000 (2000-12-15)</div></td></tr><tr style="display:none"><td colspan="2">

</td></tr></tbody></table>

In <a href="Computer_science" title="Computer science">computer science</a>, Programming Computable Functions (PCF), or Programming with Computable Functions, or Programming language for Computable Functions, is a <a href="Programming_language" title="Programming language">programming language</a> which is <a href="Type_system" title="Type system">typed</a> and based on <a href="Functional_programming" title="Functional programming">functional programming</a>, introduced by <a href="Gordon_Plotkin" title="Gordon Plotkin">Gordon Plotkin</a> in 1977,<a href="#cite_note-Plotkin_1977-1">[1]</a> based on prior unpublished material by <a href="Dana_Scott" title="Dana Scott">Dana Scott</a>.<a href="#cite_note-2">[a]</a> It can be considered as an extended version of the <a href="Typed_lambda_calculus" title="Typed lambda calculus">typed lambda calculus</a>, or a simplified version of modern typed functional languages such as <a href="ML_(programming_language)" title="ML (programming language)">ML</a> or <a href="Haskell" title="Haskell">Haskell</a>.

A <a href="Fully_abstract" class="mw-redirect" title="Fully abstract">fully abstract</a> model for PCF was first given by <a href="Robin_Milner" title="Robin Milner">Robin Milner</a>.<a href="#cite_note-Milner_1977-3">[2]</a> However, since Milner's model was essentially based on the syntax of PCF it was considered less than satisfactory.<a href="#cite_note-Ong_1995-4">[3]</a> The first two fully abstract models not employing syntax were formulated during the 1990s. These models are based on <a href="Game_semantics" title="Game semantics">game semantics</a><a href="#cite_note-Hyland_2000-5">[4]</a><a href="#cite_note-Abramsky_2000-6">[5]</a> and Kripke logical relations.<a href="#cite_note-O'Hearn_1995-7">[6]</a> For a time it was felt that neither of these models was completely satisfactory, since they were not effectively presentable. However, Ralph Loader demonstrated that no effectively presentable fully abstract model could exist, since the question of program equivalence in the finitary fragment of PCF is not decidable.<a href="#cite_note-Loader_2001-8">[7]</a>

<div class="mw-heading mw-heading2"><h2 id="Syntax">Syntax</h2></div>

The <a href="Data_type" title="Data type">data types</a> of PCF are inductively defined as

<li>For types σ and τ, there is a function type σ → τ</li></ul>

A context is a list of pairs x : σ, where x is a variable name and σ is a type, such that no variable name is duplicated. One then defines typing judgments of terms-in-context in the usual way for the following syntactical constructs:

<ul><li>Variables (if x : σ is part of a context Γ, then Γ ⊢ x : σ)</li>

<li>Application (of a term of type σ → τ to a term of type σ)</li>

<li><a href="%CE%9B-abstraction" class="mw-redirect" title="Λ-abstraction">λ-abstraction</a></li>

<li>The <a href="Fixed-point_combinator#Y_combinator" title="Fixed-point combinator">Y</a> fixed point combinator (making terms of type σ out of terms of type σ → σ)</li>

<li>The successor (succ) and predecessor (pred) operations on nat and the constant 0</li>

<li>The conditional if with the typing rule:</li></ul>

<mfrac>

<mrow>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {\Gamma \;\vdash \;t\;:{\textbf {nat}},\quad \quad \Gamma \;\vdash \;s_{0}\;:\sigma ,\quad \quad \Gamma \;\vdash \;s_{1}\;:\sigma }{\Gamma \;\vdash \;{\textbf {if}}(t,s_{0},s_{1})\;:\sigma }}}</annotation>

</semantics>

</math><img src="./7d1cd1e0aa666cff73a6cff5f550eac4d7bbc864.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:47.915ex; height:6.176ex;" alt="{\displaystyle {\frac {\Gamma \;\vdash \;t\;:{\textbf {nat}},\quad \quad \Gamma \;\vdash \;s_{0}\;:\sigma ,\quad \quad \Gamma \;\vdash \;s_{1}\;:\sigma }{\Gamma \;\vdash \;{\textbf {if}}(t,s_{0},s_{1})\;:\sigma }}}" loading="lazy"></dd>

<dd>(nats will be interpreted as booleans here with a convention like zero denoting truth, and any other number denoting falsity)</dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Semantics">Semantics</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Denotational_semantics">Denotational semantics</h3></div>

A relatively straightforward semantics for the language is the Scott model. In this model,

<ul><li>Types are interpreted as certain <a href="Domain_theory" title="Domain theory">domains</a>.

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [\![{\textbf {nat}}]\!]:=\mathbb {N} _{\bot }}</annotation>

</semantics>

</math><img src="./172645ff005d9c6b718219bfe5916ccfb9d63a68.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.571ex; height:2.843ex;" alt="{\displaystyle [\![{\textbf {nat}}]\!]:=\mathbb {N} _{\bot }}" loading="lazy"> (the natural numbers with a bottom element adjoined, with the flat ordering)</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [\![\sigma \to \tau \,]\!]}</annotation>

</semantics>

</math><img src="./6f9216cddd2bbf07883a0a6d7259a98c7127a90d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.346ex; height:2.843ex;" alt="{\displaystyle [\![\sigma \to \tau \,]\!]}" loading="lazy"> is interpreted as the domain of <a href="Scott-continuous" class="mw-redirect" title="Scott-continuous">Scott-continuous</a> functions from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [\![\sigma ]\!]\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [\![\sigma ]\!]\,}</annotation>

</semantics>

</math><img src="./a3d0b607b4da282559d62257f064d874d4778c1f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.53ex; height:2.843ex;" alt="{\displaystyle [\![\sigma ]\!]\,}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [\![\tau ]\!]\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [\![\tau ]\!]\,}</annotation>

</semantics>

</math><img src="./fa3d8b955ce6db8d09b4b1605e705ecb8b4d7d16.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.402ex; height:2.843ex;" alt="{\displaystyle [\![\tau ]\!]\,}" loading="lazy">, with the pointwise ordering.</li></ul></li>

<li>A context <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1}:\sigma _{1},\;\dots ,\;x_{n}:\sigma _{n}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{1}:\sigma _{1},\;\dots ,\;x_{n}:\sigma _{n}}</annotation>

</semantics>

</math><img src="./3141b9cb594fce4c0eae2d96c815aa5392385732.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:20.202ex; height:2.009ex;" alt="{\displaystyle x_{1}:\sigma _{1},\;\dots ,\;x_{n}:\sigma _{n}}" loading="lazy"> is interpreted as the product <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [\![\sigma _{1}]\!]\times \;\dots \;\times [\![\sigma _{n}]\!]}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [\![\sigma _{1}]\!]\times \;\dots \;\times [\![\sigma _{n}]\!]}</annotation>

</semantics>

</math><img src="./6e22396cfb4399fd87de4bf7388afd3409997e09.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.248ex; height:2.843ex;" alt="{\displaystyle [\![\sigma _{1}]\!]\times \;\dots \;\times [\![\sigma _{n}]\!]}" loading="lazy"></li>

<li>Terms in context <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Gamma \;\vdash \;x\;:\;\sigma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Gamma \;\vdash \;x\;:\;\sigma }</annotation>

</semantics>

</math><img src="./431bc29fb58179b629b83c2f987c763bb98b5634.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:11.341ex; height:2.176ex;" alt="{\displaystyle \Gamma \;\vdash \;x\;:\;\sigma }" loading="lazy"> are interpreted as continuous functions <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [\![\Gamma ]\!]\;\to \;[\![\sigma ]\!]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [\![\Gamma ]\!]\;\to \;[\![\sigma ]\!]}</annotation>

</semantics>

</math><img src="./a7ade925a4ceea33e5b118ee2c54a171c2cf15a4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.313ex; height:2.843ex;" alt="{\displaystyle [\![\Gamma ]\!]\;\to \;[\![\sigma ]\!]}" loading="lazy">

<ul><li>Variable terms are interpreted as projections</li>

<li>Lambda abstraction and application are interpreted by making use of the <a href="Cartesian_closed" class="mw-redirect" title="Cartesian closed">cartesian closed</a> structure of the category of domains and continuous functions</li>

<li>Y is interpreted by taking the <a href="Least_fixed_point" title="Least fixed point">least fixed point</a> of the argument</li></ul></li></ul>

This model is not fully abstract for PCF; but it is fully abstract for the language obtained by adding a <a href="Parallel_or" class="mw-redirect" title="Parallel or">parallel or</a> operator to PCF.<a href="#cite_note-Hyland_2000-5">[4]</a>: 293

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-lower-alpha">

<li id="cite_note-2"><a href="#cite_ref-2">^</a> "PCF is a programming language for computable functions, based on LCF, Scott’s logic of computable functions."<a href="#cite_note-Plotkin_1977-1">[1]</a> Programming Computable Functions is used by (<a href="#CITEREFMitchell1996">Mitchell 1996</a>).

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFPlotkin1977" class="citation journal cs1"><a href="Gordon_Plotkin" title="Gordon Plotkin">Plotkin, Gordon D.</a> (December 1977). <a rel="nofollow" class="external text" href="http://homepages.inf.ed.ac.uk/gdp/publications/LCF.pdf">"LCF considered as a programming language"</a> (PDF). Theoretical Computer Science. 5 (3): 223–255. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0304-3975%2877%2990044-5">10.1016/0304-3975(77)90044-5</a>.</cite>

</li>

<li id="cite_note-Milner_1977-3"><a href="#cite_ref-Milner_1977_3-0">^</a> <cite id="CITEREFMilner1977" class="citation journal cs1"><a href="Robin_Milner" title="Robin Milner">Milner, Robin</a> (February 1977). <a rel="nofollow" class="external text" href="https://www.pure.ed.ac.uk/ws/files/15112912/1_s2.0_0304397577900536_main.pdf">"Fully abstract models of typed λ-calculi"</a> (PDF). Theoretical Computer Science. 4 (1): 1–22. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0304-3975%2877%2990053-6">10.1016/0304-3975(77)90053-6</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/20.500.11820%2F731c88c6-cdb1-4ea0-945e-f39d85de11f1">20.500.11820/731c88c6-cdb1-4ea0-945e-f39d85de11f1</a>.</cite>

</li>

<li id="cite_note-Ong_1995-4"><a href="#cite_ref-Ong_1995_4-0">^</a> <cite id="CITEREFOng1995" class="citation book cs1">Ong, C.-H. L. (1995). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20060107195328/http://users.comlab.ox.ac.uk/luke.ong/publications/">"Correspondence between Operational and Denotational Semantics: The Full Abstraction Problem for PCF"</a>. In Abramsky, S.; Gabbay, D.; Maibau, T. S. E. (eds.). Handbook of Logic in Computer Science. Oxford University Press. pp. 269–356. Archived from <a rel="nofollow" class="external text" href="http://users.comlab.ox.ac.uk/luke.ong/publications/">the original</a> on 2006-01-07. Retrieved 2006-01-19.</cite>

</li>

<li id="cite_note-Hyland_2000-5">^ <a href="#cite_ref-Hyland_2000_5-0">a</a> <a href="#cite_ref-Hyland_2000_5-1">b</a> <cite id="CITEREFHylandOng2000" class="citation journal cs1">Hyland, J. M. E.; Ong, C.-H. L. (15 December 2000). <a rel="nofollow" class="external text" href="https://ora.ox.ac.uk/objects/uuid:63c54392-39f3-46f1-8a68-e6ff0ec90218">"On Full Abstraction for PCF"</a>. Information and Computation. 163 (2): 285–408. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Finco.2000.2917">10.1006/inco.2000.2917</a>.</cite>

</li>

<li id="cite_note-Abramsky_2000-6"><a href="#cite_ref-Abramsky_2000_6-0">^</a> <cite id="CITEREFAbramskyJagadeesanMalacaria2000" class="citation journal cs1">Abramsky, S.; Jagadeesan, R.; Malacaria, P. (15 December 2000). <a rel="nofollow" class="external text" href="http://qmro.qmul.ac.uk/xmlui/handle/123456789/13604">"Full Abstraction for PCF"</a>. Information and Computation. 163 (2): 409–470. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Finco.2000.2930">10.1006/inco.2000.2930</a>.</cite>

</li>

<li id="cite_note-O'Hearn_1995-7"><a href="#cite_ref-O'Hearn_1995_7-0">^</a> <cite id="CITEREFO'HearnRiecke1995" class="citation journal cs1">O'Hearn, P. W.; Riecke, J. G. (1995). <a rel="nofollow" class="external text" href="https://surface.syr.edu/lcsmith_other/3">"Kripke Logical Relations and PCF"</a>. Information and Computation. 120 (1): 107–116. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Finco.1995.1103">10.1006/inco.1995.1103</a>.</cite>

</li>

<li id="cite_note-Loader_2001-8"><a href="#cite_ref-Loader_2001_8-0">^</a> <cite id="CITEREFLoader2001" class="citation journal cs1">Loader, R. (2001). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0304-3975%2800%2900194-8">"Finitary PCF is not decidable"</a>. Theoretical Computer Science. 266 (1–2): 341–364. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0304-3975%2800%2900194-8">10.1016/S0304-3975(00)00194-8</a>.</cite>

</li>

</ol></div></div>

<ul><li><cite id="CITEREFScott1969" class="citation journal cs1"><a href="Dana_Scott" title="Dana Scott">Scott, Dana S.</a> (1969). <a rel="nofollow" class="external text" href="https://www.cs.cmu.edu/~kw/scans/scott93tcs.pdf">"A type-theoretic alternative to CUCH, ISWIM, OWHY"</a> (PDF). Unpublished Manuscript.</cite> Appeared as <cite id="CITEREFScott1993" class="citation journal cs1"><a href="Dana_Scott" title="Dana Scott">Scott, Dana S.</a> (1993). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0304-3975%2893%2990095-b">"A type-theoretic alternative to CUCH, ISWIM, OWHY"</a>. <a href="Theoretical_Computer_Science_(journal)" title="Theoretical Computer Science (journal)">Theoretical Computer Science</a>. 121: 411–440. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0304-3975%2893%2990095-b">10.1016/0304-3975(93)90095-b</a>.</cite></li>

<li><cite id="CITEREFMitchell1996" class="citation book cs1"><a href="John_C._Mitchell" title="John C. Mitchell">Mitchell, John C.</a> (1996). <a rel="nofollow" class="external text" href="https://theory.stanford.edu/~jcm/books/fpl-chap2.ps">"The Language PCF"</a>. Foundations for Programming Languages. MIT Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780262133210</bdi>.</cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://www.cs.bham.ac.uk/~mhe/papers/RNC3.pdf">Introduction to RealPCF</a></li>

<li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20071213234103/http://www.cs.pomona.edu/classes/cs131/Parsers/parsePCF.sml">Lexer and Parser for PCF written in SML</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-06" href="https://en.wikipedia.org/wiki/?title=Programming_Computable_Functions&oldid=1299089181">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>